Une fonction calculable (ou fonction récursive) est une fonction semi-calculable (ou fonction partielle récursive) qui est aussi totale, c`est-à-dire définie sur tout son domaine. Ce sont les fonctions calculées par une machine de Turing « qui termine ».